package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: shm
 * @dateTime: 2020/11/4 9:14
 * @description: 57. 插入区间
 * 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
 *
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 *
 * 示例 1：
 *
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出：[[1,5],[6,9]]
 * 示例 2：
 *
 * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出：[[1,2],[3,10],[12,16]]
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 *
 * 注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
 */
public class Insert {
    /**
     * @author: shm
     * @dateTime: 2020/11/4 11:37
     * @description: 前言
     * 对于区间 S_1 = [l_1, r_1]S
     * 1
     * ​
     *  =[l
     * 1
     * ​
     *  ,r
     * 1
     * ​
     *  ] 和 S_2 = [l_2, r_2]S
     * 2
     * ​
     *  =[l
     * 2
     * ​
     *  ,r
     * 2
     * ​
     *  ]，如果它们之间没有重叠（没有交集），说明要么 S_1S
     * 1
     * ​
     *   在 S_2S
     * 2
     * ​
     *   的左侧，此时有 r_1 < l_2r
     * 1
     * ​
     *  <l
     * 2
     * ​
     *  ；要么 S_1S
     * 1
     * ​
     *   在 S_2S
     * 2
     * ​
     *   的右侧，此时有 l_1 > r_2l
     * 1
     * ​
     *  >r
     * 2
     * ​
     *  。
     *
     * 如果 r_1 < l_2r
     * 1
     * ​
     *  <l
     * 2
     * ​
     *   和 l_1 > r_2l
     * 1
     * ​
     *  >r
     * 2
     * ​
     *   二者均不满足，说明 S_1S
     * 1
     * ​
     *   和 S_2S
     * 2
     * ​
     *   必定有交集，它们的交集即为
     *
     * [\max(l_1, l_2), \min(r_1, r_2)]
     * [max(l
     * 1
     * ​
     *  ,l
     * 2
     * ​
     *  ),min(r
     * 1
     * ​
     *  ,r
     * 2
     * ​
     *  )]
     *
     * 并集即为
     *
     * [\min(l_1, l_2), \max(r_1, r_2)]
     * [min(l
     * 1
     * ​
     *  ,l
     * 2
     * ​
     *  ),max(r
     * 1
     * ​
     *  ,r
     * 2
     * ​
     *  )]
     *
     * 方法一：模拟
     * 思路与算法
     *
     * 在给定的区间集合 \mathcal{X}X 互不重叠的前提下，当我们需要插入一个新的区间 S = [\textit{left}, \textit{right}]S=[left,right] 时，我们只需要：
     *
     * 找出所有与区间 SS 重叠的区间集合 \mathcal{X}'X
     * ′
     *  ；
     * 将 \mathcal{X}'X
     * ′
     *   中的所有区间连带上区间 SS 合并成一个大区间；
     * 最终的答案即为不与 \mathcal{X}'X
     * ′
     *   重叠的区间以及合并后的大区间。
     *
     *
     * 这样做的正确性在于，给定的区间集合中任意两个区间都是没有交集的，因此所有需要合并的区间，就是所有与区间 SS 重叠的区间。
     *
     * 并且，在给定的区间集合已经按照左端点排序的前提下，所有与区间 SS 重叠的区间在数组 \textit{intervals}intervals 中下标范围是连续的，因此我们可以对所有的区间进行一次遍历，就可以找到这个连续的下标范围。
     *
     * 当我们遍历到区间 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 时：
     *
     * 如果 r_i < \textit{left}r
     * i
     * ​
     *  <left，说明 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 与 SS 不重叠并且在其左侧，我们可以直接将 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 加入答案；
     *
     * 如果 l_i > \textit{right}l
     * i
     * ​
     *  >right，说明 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 与 SS 不重叠并且在其右侧，我们可以直接将 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 加入答案；
     *
     * 如果上面两种情况均不满足，说明 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 与 SS 重叠，我们无需将 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 加入答案。此时，我们需要将 SS 与 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 合并，即将 SS 更新为其与 [l_i, r_i][l
     * i
     * ​
     *  ,r
     * i
     * ​
     *  ] 的并集。
     *
     * 那么我们应当在什么时候将区间 SS 加入答案呢？由于我们需要保证答案也是按照左端点排序的，因此当我们遇到第一个 满足 l_i > \textit{right}l
     * i
     * ​
     *  >right 的区间时，说明以后遍历到的区间不会与 SS 重叠，并且它们左端点一定会大于 SS 的左端点。此时我们就可以将 SS 加入答案。特别地，如果不存在这样的区间，我们需要在遍历结束后，将 SS 加入答案。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{intervals}intervals 的长度，即给定的区间个数。
     *
     * 空间复杂度：O(1)O(1)。除了存储返回答案的空间以外，我们只需要额外的常数空间即可。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/insert-interval/solution/cha-ru-qu-jian-by-leetcode-solution/
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean place = false;
        List<int[]> ansList = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[0]>right){
                if (!place){
                    ansList.add(new int[]{left,right});
                    place = true;
                }
                ansList.add(interval);
            }else if (interval[1]<left){
                ansList.add(interval);
            }else {
                left=Math.min(left,interval[0]);
                right=Math.max(right,interval[1]);
            }
        }
        if (!place){
            ansList.add(new int[]{left,right});
        }
        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); i++) {
            ans[i]=ansList.get(i);
        }
        return ans;
    }
}
